// https://leetcode.cn/problems/longest-increasing-subsequence/
// Created by ade on 2022/9/19.
// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
//
//子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
// 输入：nums = [10,9,2,5,3,7,101,18] 10 | 9 | 2,5 | 3,7,101 | 18
//输出：4
//解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
// 输入：nums = [0,1,0,3,2,3]
//输出：4
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 动态规划
    int lengthOfLIS(vector<int> &nums) {
        int len = nums.size();
        vector<int> dp(len, 1);
        int maxN = 0;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
            }
            maxN = max(dp[i], maxN);
        }
        return maxN;
    }


};

int main() {
    vector<int> nums = {1, 3, 6, 7, 9, 4, 10, 5, 6};
    Solution so;
    cout << so.lengthOfLIS(nums);
    return 0;
}